import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/22 9:53
 * @description 哈希表 + 二分查找
 */
public class Solution {

    class Node {
        String k, v;
        int t;

        Node(String _k, String _v, int _t) {
            k = _k;
            v = _v;
            t = _t;
        }
    }

    /**
     * 哈希表 + 动态数组
     */
    Map<String, List<Node>> map = new HashMap<>();

    /**
     * 存储k v t时，O(1)复杂度找到key对应的数组，因为t递增，O(1)复杂度加入到数组末尾
     * @param k key
     * @param v value
     * @param t timestamp
     */
    public void set(String k, String v, int t) {
        List<Node> list = map.getOrDefault(k, new ArrayList<>());
        list.add(new Node(k, v, t));
        map.put(k, list);
    }

    /**
     * 以O(1)复杂度找到key对应的数组，因为t递增，采用二分查找找到 <=t的 最大值 时间O(logn)
     * @param k key
     * @param t value
     * @return timestamp
     */
    public String get(String k, int t) {
        List<Node> list = map.getOrDefault(k, new ArrayList<>());
        if (list.isEmpty()) return "";
        int n = list.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (list.get(mid).t <= t) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return list.get(r).t <= t ? list.get(r).v : "";
    }
}
